package graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 基于邻接表的有权无向图
 */
public class WeightedTGraph {
    /**
     * 顶点数
     */
    private final int V;

    /**
     * 边数
     */
    private int E;

    /**
     * 邻接表节点
     */
    class Edge {
        int w;
        int v;
        int weight;
        Edge next;

        public Edge(int v, int w, int weight, Edge next) {
            this.v = v;
            this.w = w;
            this.weight = weight;
            this.next = next;
        }

        public Edge() {
        }

    }

    /**
     * 邻接表
     */
    private Edge[] adjacencyTable;

    /**
     * 构造函数
     * 
     * @param v 顶点数
     */
    public WeightedTGraph(int v) {
        this.V = v;
        this.adjacencyTable = new Edge[v];
        for (int i = 0; i < v; i++) {
            this.adjacencyTable[i] = new Edge(i + 1, i + 1, 0, null);
        }
    }

    /**
     * 验证输出顶点的正确性
     * 
     * @param v
     * @return
     */
    public boolean validateV(int v) {
        if (v < 1 || v > this.V) {
            System.out.println("请输入在1到" + V + "之间的顶点");
            return false;
        } else {
            return true;
        }
    }

    /**
     * 添加边，联通v和w
     * 
     * @param v
     * @param w
     */
    public void addEdge(int start, int end, int weight) {
        if (validateV(start) && validateV(end)) {
            Edge tmp = this.adjacencyTable[start - 1].next;
            this.adjacencyTable[start - 1].next = new Edge(start, end, weight, null);
            this.adjacencyTable[start - 1].next.next = tmp;

            tmp = this.adjacencyTable[end - 1].next;
            this.adjacencyTable[end - 1].next = new Edge(end, start, weight, null);
            this.adjacencyTable[end - 1].next.next = tmp;
            E++;
        }
    }

    /**
     * 获取顶点数
     */
    public int V() {
        return V;
    }

    /**
     * 获取边数
     * 
     * @return
     */
    public int E() {
        return E;
    }

    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < this.adjacencyTable.length; i++) {
            buffer.append(this.adjacencyTable[i].w + ":");
            Edge tmp = this.adjacencyTable[i].next;
            while (tmp != null) {
                buffer.append(" (" + tmp.w + "," + tmp.weight + ")");
                tmp = tmp.next;
            }
            buffer.append("\n");
        }
        return buffer.toString();
    }

    /**
     * 获取v的所有邻接节点
     * 
     * @param v
     * @return 二维数组，第一维是邻接节点编号，第二维对应的是权重
     */
    public int[][] adj(int v) {
        if (validateV(v)) {
            int[] tmp = new int[this.V];
            int[] weight = new int[this.V];
            int count = 0;
            Edge hNode = adjacencyTable[v - 1].next;
            while (hNode != null) {
                tmp[count] = hNode.w;
                weight[count] = hNode.weight;
                count++;
                hNode = hNode.next;
            }
            int[][] returnValue = new int[2][count];
            for (int i = 0; i < count; i++) {
                returnValue[0][i] = tmp[i];
                returnValue[1][i] = weight[i];
            }
            return returnValue;
        } else {
            return null;
        }
    }

    /**
     * 获取节点v的度
     * 
     * @param v
     * @return
     */
    public int getDegree(int v) {
        if (validateV(v)) {
            return adj(v).length;
        } else {
            return 0;
        }
    }

    /**
     * 深度优先搜索
     * 
     * @param v 深度优先搜索开始的点
     * @return
     */
    public void DFS(int v) {
        boolean[] visited = new boolean[this.V];
        DFSHelper(visited, v);
    }

    /**
     * 深度优先搜索的辅助实现函数
     * 
     * @param visited 存储着是否被遍历的数据
     * @param v       当前遍历节点
     */
    public void DFSHelper(boolean[] visited, int v) {
        if (visited[v - 1] == false) {
            visited[v - 1] = true;
            System.out.println(v);
            for (int i : this.adj(v)[0]) {
                DFSHelper(visited, i);
            }
        }
    }

    /**
     * 广度优先搜索
     * 
     * @param v 从v点开始的广度优先搜索
     */
    public void BFS(int v) {
        boolean[] visited = new boolean[this.V];
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(v);

        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            if (visited[tmp - 1] == false) {
                visited[tmp - 1] = true;
                System.out.println(tmp);
                for (int i : this.adj(tmp)[0]) {
                    queue.add(i);
                }
            }
        }
    }

    /**
     * 有权图单源最短路径算法
     * 
     * @param v
     */
    public int[] singleSourceShortestPath(int v) {
        return Dijkstra(v);
    }

    /**
     * 有权图单源最短路径算法Dijkstra
     * 
     * @param v
     */
    public int[] Dijkstra(int v) {
        // 初始化工作
        boolean[] collected = new boolean[this.V];
        collected[v - 1] = true;

        int[] dist = new int[this.V];
        for (int i = 0; i < dist.length; i++) {
            dist[i] = Integer.MAX_VALUE / 2;
        }
        dist[v - 1] = 0;
        int[] path = new int[this.V];
        for (int i = 0; i < path.length; i++) {
            path[i] = -1;
        }

        int[][] tmp = this.adj(v);
        for (int i = 0; i < tmp[0].length; i++) {
            dist[tmp[0][i] - 1] = tmp[1][i];
            path[tmp[0][i] - 1] = v;
        }

        // 开始
        while (true) {
            // 在未被收录的集合中寻找距离最短的
            int minIndex = v - 1;
            int minValue = Integer.MAX_VALUE / 2;
            for (int i = 0; i < dist.length; i++) {
                if (collected[i] == false && dist[i] <= minValue) {
                    minIndex = i;
                    minValue = dist[i];
                }
            }
            // 找不到就退出
            if (minIndex == v - 1) {
                break;
            }
            // 找到了就标志, 并更换下标
            minIndex++;
            collected[minIndex - 1] = true;
            // 得到该点的所有邻接节点及其权重
            tmp = this.adj(minIndex);
            // 遍历所有邻接节点
            for (int i = 0; i < tmp[0].length; i++) {
                if (dist[minIndex - 1] + tmp[1][i] < dist[tmp[0][i] - 1]) {
                    dist[tmp[0][i] - 1] = dist[minIndex - 1] + tmp[1][i];
                    path[tmp[0][i] - 1] = minIndex;
                }
            }
        }
        return dist;
    }

    /**
     * 有权图多源最短路径算法
     * 
     * @return 最短路径矩阵
     */
    public int[][] multiSourceShortestPath() {
        int[][] shortestPath = new int[this.V][this.V];
        for (int i = 0; i < this.V; i++) {
            shortestPath[i] = singleSourceShortestPath(i + 1);
        }
        return shortestPath;
    }

    /**
     * Minimum Scanning Tree 最小生成树 Tree: V个顶点有V-1条边，无回路 Scanning:
     * 包含全部顶点，V-1条边全部都在顶点里 Minimun：边的权重和最小
     * 
     * @return 最小生成树的边的连线，第一维是from点，第二维是to点
     */
    public int[][] MST() {
        return kruskal();
    }

    /**
     * 最小生成树算法Kruskal, 时间复杂度为 E^2, E为边的个数，因此适用于稀疏图
     * 
     * @return
     */
    public int[][] kruskal() {
        Edge[] edges = new Edge[this.E];
        int count = 0;
        int[] vset = new int[this.V];
        int[][] out = new int[2][this.V - 1];
        // 初始化边
        for (int i = 0; i < this.adjacencyTable.length; i++) {
            Edge tmp = this.adjacencyTable[i].next;
            while (tmp != null) {
                // 防止选取重复的
                if (tmp.w > tmp.v) {
                    edges[count] = tmp;
                    count++;
                }
                tmp = tmp.next;
            }
            vset[i] = i;
        }

        // 边排序
        for (int i = 0; i < edges.length; i++) {
            for (int j = i + 1; j < edges.length; j++) {
                if (edges[i].weight > edges[j].weight) {
                    Edge tmp = edges[i];
                    edges[i] = edges[j];
                    edges[j] = tmp;
                }
            }
        }

        count = 0;
        int num = 0;
        while (count < edges.length) {
            // 检测是否成环
            if (vset[edges[count].v - 1] != vset[edges[count].w - 1]) {
                out[0][num] = edges[count].v;
                out[1][num] = edges[count].w;
                // 合并为1棵树
                for (int i = 0; i < vset.length; i++) {
                    if (vset[i] == vset[edges[count].w - 1]) {
                        vset[i] = vset[edges[count].v - 1];
                    }
                }
                num++;
            }
            count++;
        }
        if (num != this.V - 1) {
            System.out.println("不存在最小生成树!");
            return null;
        }
        return out;
    }
}